//
// Created by user on 2022/2/16.
//

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;//库里自带的算法
bool cmp(int a,int b)
{
    return a>b;
}
void sortColors(vector<int>& nums) {
//    sort(nums.begin(), nums.end(), greater<int>());
    sort(nums.begin(), nums.end(), cmp);

}

//计数排序
void sortColors1(vector<int>& nums) {
    // 1. 计数
    int* count = new int[3];
    for (int num : nums) {
        count[num]++;
    }
    // 2. 排序
    int k = 0;
    for (int i = 0; i <= 2; i++) {
        int num = count[i];
        for (int j = 1; j <= num; j++) {
            nums[k++] = i;
        }
    }
}

//三路快排
void threeQuickSort(vector<int>&nums, int lo, int hi){
    if (lo>=hi){
        return;
    }
    int index = rand()%(hi-lo+1)+lo;
    swap(nums[index], nums[hi]);
    int pivot = nums[hi];


    int less = lo;
    int great = hi;
    int i = lo;
    //排序
    while (i<=great){
        if(nums[i]<pivot){
            swap(nums[i], nums[less]);
            less++;
            i++;
        }else if(nums[i]>pivot){
            swap(nums[i], nums[great]);
            great--;
        }else{
            i++;
        }
    }
    threeQuickSort(nums, lo, less-1);
    threeQuickSort(nums, great+1, hi);
}

void sortColors2(vector<int>& nums) {
    // 1. 计数
    threeQuickSort(nums, 0, nums.size()-1);
}